package middle;

/**
 * 给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
 *
 * 必须在不使用库的sort函数的情况下解决这个问题。
 *
 * 链接：https://leetcode.cn/problems/sort-colors
 *
 * @author yuxuan.hu
 * */
public class SortColors {
    /**
     * 这道题可以理解为将0、1、2分成三个区域
     * 然后我们把0和2的区域找出来了，不就每个区域都找出来了吗
     * 定义一个变量i,代表当前的元素下标
     * 定义一个指针p0，表示区域0的最后一个元素位置
     * 定义一个指针p2, 表示p2区域的第一个元素位置
     * */
    class Solution {
        public void sortColors(int[] nums) {
            int p0 = 0;
            int p2 = nums.length-1;
            for (int i = 0; i < nums.length; i++) {
                // 这里为什么用while呢？可以试想一下用if的时候，p2指向的元素为2
                while(i <= p2 && nums[i] == 2){
                    nums[i] = nums[p2];
                    nums[p2] = 2;
                    p2--;
                }
                // 这里为什么用就可以用if呢？ 因为i跟p0是一个起点，这样i指向的元素不为0，那么p0肯定也不为0
                if(nums[i] == 0){
                    nums[i] = nums[p0];
                    nums[p0] = 0;
                    p0++;
                }
            }
        }
    }

    /**
     * 其实按照上面的方法，我们也可以找出0和1的区域
     * 定义一个变量i用来遍历
     * 定义一个指针p0  表示p0之前的元素都为0
     * 同理，定义一个指针p1  表示p1之前 and p0之后的元素都为1
     * */
    class Solution1 {
        public void sortColors(int[] nums) {
            int p0 = 0;
            int p1 = 0;

            for (int i = 0; i < nums.length; i++) {
                if(nums[i] == 0){
                    nums[i] = nums[p0];
                    nums[p0] = 0;
                    // 为什么需要加这个判断。实际上，当p1位置大于p0的时候，说明p0指向的肯定是1，那么p0和nums[i]进行交换过后，nums[i]就需要和p1交换
                    if(p0 < p1){
                        nums[i] = nums[p1];
                        nums[p1] = 1;
                    }
                    p0++;
                    p1++;
                }else if (nums[i] == 1){
                    nums[i] = nums[p1];
                    nums[p1] = 1;
                    p1++;
                }
            }
        }
    }
}
